/**
 * 思路 
1 堆排序
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
 */
var findKthLargest = function(nums, k) {
  const heap = nums.slice(0, k);
  // 建堆
  for (let i = Math.floor((k - 2) / 2); i >= 0; i--) {
    heapify(heap, i, k);
  }
  for(let i = k; i < nums.length; i++) {
    if(nums[i] > heap[0]) {
      heap[0] = nums[i];
      heapify(heap, 0, k); // 1是要调整的位置
    }
  }
  return heap[0];
};
var heapify = function(heap, i, heapSize) {
  while (true) {
    let min = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < heapSize && heap[left] < heap[min]) min = left;
    if (right < heapSize && heap[right] < heap[min]) min = right;
    if (min !== i) {
      [heap[i], heap[min]] = [heap[min], heap[i]];
      i = min;
    } else {
      break;
    }
  }
}
const nums = [3,2,1,5,6,4];
const k = 2;
console.log(findKthLargest(nums, k));